package 力扣_树算法.遍历.根据遍历构建二叉树;


import java.util.HashMap;
import java.util.Map;

/**889. 根据前序和后序遍历构造二叉树
 * @author zx
 * @create 2022-04-14 10:25
 */
public class Num889 {
    /**
     * 这三道题需要借助图去理解：
     * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal
       /solution/tu-jie-889-gen-ju-qian-xu-he-hou-xu-bian-li-gou-2/
     * 解释唯一性：
     * 前序遍历的特点是根节点始终出现在第一位
     * 后序遍历的特点是根节点始终出现在最后一位
     * 前序和后序都只用于提供根结点，只有中序才能区分左右子树。
     * 因为有了中序序列，得到根结点在中序中的位置后，根结点左边的一定都是左子树结点，右边的一定都是右子树结点，
     * 这是由中序定义的左->中->右遍历顺序决定好了的。
     * 所以我们可以严格区分出左右子树，递归地构建出唯一的二叉树。
     * 值得注意的是，本题的前序+后序是不能构建唯一的二叉树的。
     * 文章来源：
     * https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-postorder-traversal
       /solution/marvelzhong-deng-de-xue-xi-bi-ji-889-by-tyanyone-2/
     */
    /**
     * 本地代码和前面的代码最像, 面试时最好写; 根据AI解释下面代码
     */
    private int index = 0;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode constructFromPrePost(int[] preorder, int[] postorder) {
        for(int i = 0;i < postorder.length;i++){
            map.put(postorder[i],i);
        }
        return buildTree(preorder,0,postorder.length - 1);
    }
    private TreeNode buildTree(int[] preorder, int left, int right){
        if(left > right){
            return null;
        }
        // 创建当前子树的根节点
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        // left == right：当前节点是叶子节点,直接返回该节点(无左右子树)
        if(left == right){
            return root;
        }
        // 如果左子树存在,preorder[index]是左子树的根节点(根->左->右)
        int pos = map.get(preorder[index]);//这里必须为：preorder[index]
        // pos：postorder中root的左子树的最后一个节点是左子树的根节点
        root.left = buildTree(preorder,left,pos);
        // right - 1：postorder的最后一个节点是当前子树的根节点,所以右子树的范围排除它(左->右->根)
        root.right = buildTree(preorder,pos + 1,right - 1);
        return root;
    }
}
